package com.demo.jdksource;

import java.util.Map;
import java.util.Objects;

/**
 * 重写Hashmap
 * 。而JDK1.8中，HashMap采用位桶+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。
 */
public class MyHashMap<K,V> {

    transient Node<K,V>[] table; //存储（位桶）的数组</k,v>

    //源码英文注释均舍去
    //初始化Node数组容量16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    //初始化最大的数组容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    //初始化负载因子0.75
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //由链表转红黑树的临界值
    static final int TREEIFY_THRESHOLD = 8;
    //由红黑树转链表的临界值
    static final int UNTREEIFY_THRESHOLD = 6;
    //桶可能被转化为树形结构的最小容量的临界值
    static final int MIN_TREEIFY_CAPACITY = 64;
    //计数器
    transient int modCount;
    //Node数组扩容的临界值
    int threshold;

    /**
     * The load factor for the hash table.
     *
     * @serial
     */
    final float loadFactor;

    /**
     * Constructs an empty <tt>HashMap</tt> with the default initial capacity
     * (16) and the default load factor (0.75).
     */
    public MyHashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    /**
     * The number of key-value mappings contained in this map.
     */
    transient int size;


    // Create a regular (non-tree) node
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
        return new Node<>(hash, key, value, next);
    }

    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    /**
     * 1 判断表或ke对应的下的索引引用是否是null，如果是直接返回null
     *2 判断索引处第一个key与传入key是否相等，如果相等直接返回
     *3 如果不相等，判断链表是否是红黑二叉树，如果是，直接从树中取值
     *4 如果不是树，就遍历链表查找
     * @param hash
     * @param key
     * @return
     */

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//如果表不是空的，并且要查找索引处有值，就判断位于第一个的key是否是要查找的key
        if ((tab = table) != null &&
                (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null
          ) {
            if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k))))
//如果是，就直接返回
                return first;
//如果不是就判断链表是否是红黑二叉树，如果是，就从树中取值
            if ((e = first.next) != null) {
//                if (first instanceof TreeNode){
//                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//                }


//如果不是树，就遍历链表
                do {
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

    /**
     * ①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
     *
     * ②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，
     * 直接新建节点添加，转向⑥，如果table[i]不为空，转向③；
     *
     * ③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，
     * 这里的相同指的是hashCode以及equals；
     *
     * ④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
     *
     * ⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
     *
     * ⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
     *
     * 具体源码如下：
     *
     *
     * @param hash
     * @param key
     * @param value
     * @param onlyIfAbsent
     * @param evict
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                  boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 步骤①：tab为空则创建
        // table未初始化或者长度为0，进行扩容
        if ((tab = table) == null || (n = tab.length) == 0){
            n = (tab = resize()).length;
        }

        // 步骤②：计算index，并对null做处理
        // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
            // 桶中已经存在元素
        else {
            Node<K,V> e; K k;
            // 步骤③：节点key存在，直接覆盖value
            // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                // 将第一个元素赋值给e，用e来记录
                e = p;
                // 步骤④：判断该链为红黑树
                // hash值不相等，即key不相等；为红黑树结点
//            else if (p instanceof TreeNode)
//                // 放入树中
//                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//                // 步骤⑤：该链为链表
//                // 为链表结点
             else {
                // 在链表最末插入结点
                for (int binCount = 0; ; ++binCount) {
                    // 到达链表的尾部
                    if ((e = p.next) == null) {
                        // 在尾部插入新结点
                        p.next = newNode(hash, key, value, null);
                        // 结点数量达到阈值，转化为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //treeifyBin(tab, hash);
                           // 跳出循环
                        break;
                    }
                    //如果在没有到达链表尾节点之前，就相同，就覆盖。
                    // 判断链表中结点的key值与插入的元素的key值是否相等
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k)))){
                        // 相等，跳出循环
                        break;
                    }
                    // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                    p = e;
                }
            }
            // 表示在桶中找到key值、hash值与插入元素相等的
            ////如果e不是null，说明没有迭代到最后就跳出了循环，说明链表中有相同的key，因此只需要将value覆盖，并将oldValue返回即可
            if (e != null) {
                // 记录e的value
                V oldValue = e.value;
                // onlyIfAbsent为false或者旧值为null
                if (!onlyIfAbsent || oldValue == null)
                    //用新值替换旧值
                    e.value = value;
                // 访问后回调
                afterNodeAccess(e);
                // 返回旧值
                return oldValue;
            }
        }

        // 结构性修改 //说明没有key相同，因此要插入一个key-value，并记录内部结构变化次数
        ++modCount;
        // 步骤⑥：超过最大容量 就扩容
        // 实际大小大于阈值则扩容
        if (++size > threshold)
            resize();
        // 插入后回调
        afterNodeInsertion(evict);
        return null;
    }


    // Callbacks to allow LinkedHashMap post-actions
    void afterNodeAccess(Node<K,V> p) { }
    void afterNodeInsertion(boolean evict) { }
    void afterNodeRemoval(Node<K,V> p) { }


    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and load factor.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public MyHashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                    initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                    loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

    /**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }


    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and the default load factor (0.75).
     *
     * @param  initialCapacity the initial capacity.
     * @throws IllegalArgumentException if the initial capacity is negative.
     */
    public MyHashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * 在putVal()中，我们看到在这个函数里面使用到了2次resize()方法，
     * resize()方法表示的在进行第一次初始化时会对其进行扩容，
     * 或者当该数组的实际大小大于其临界值值(第一次为12),
     * 个时候在扩容的同时也会伴随的桶上面的元素进行重新分发，这也是JDK1.8版本的一个优化的地方，在1.7中，扩容之后需要重新去计算其Hash值，根据Hash值对其进行分发，但在1.8版本中，则是根据在同一个桶的位置中进行判断(e.hash & oldCap)是否为0，
     * 重新进行hash分配后，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上
     */
    public  final Node<K,V>[] resize(){
        Node<K,V>[] oldTab = table; //当前所有元素所在的数组，称为老的元素数组
        int oldCap = (oldTab == null) ? 0 : oldTab.length; //老的元素数组长度
        int oldThr = threshold;	// 老的扩容阀值设置
        int newCap, newThr = 0;	// 新数组的容量，新数组的扩容阀值都初始化为0
        if (oldCap > 0) { // 如果老数组长度大于0，说明已经存在元素
            // PS1，  //超过最大容量，不再进行扩充
            if (oldCap >= MAXIMUM_CAPACITY) {  // 如果数组元素个数大于等于限定的最大容量（2的30次方）
                threshold = Integer.MAX_VALUE; // 扩容阀值设置为int最大值（2的31次方 -1 ），因为oldCap再乘2就溢出了 。
                return oldTab; // 返回老的元素数组
            }
           /*
            * 如果数组元素个数在正常范围内，那么新的数组容量为老的数组容量的2倍（左移1位相当于乘以2）
      * 如果扩容之后的新容量小于最大容量  并且  老的数组容量大于等于默认初始化容量（16），
               那么新数组的扩容阀值设置为老阀值的2倍。（老的数组容量大于16意味着：要么构造函数指定了一个大于16的初始化容量值，
               要么已经经历过了至少一次扩容）

              优化： 这里把乘以2倍，赋值 和比较 都放在一行代码上，精简了代码 (newCap = oldCap << 1) < MAXIMUM_CAPACITY
         newCap = oldCap << 1
                 newCap < MAXIMUM_CAPACITY
             */
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY
                    &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY){
                  newThr = oldThr << 1; // double threshold
             }
        }

        // PS2 （说明老数组还没有添加任何元素）
        // 运行到这个else if  说明老数组还没有添加任何元素
        // 如果老数组的扩容阀值大于0，那么设置新数组的容量为该阀值
         // 这一步也就意味着构造该map的时候，指定了初始化容量。如果是16，那么这里就是12
        else if (oldThr > 0) { // 构造了map的时候，指定了初始化容量，然后法制就是2的N次方
            newCap = oldThr;
        }
        else {
            //没有构造函数会进入的逻辑
            // new hashmap zero initial threshold signifies using defaults
          // 能运行到这里的话，说明是调用无参构造函数创建的该map，并且第一次添加元素
            newCap = DEFAULT_INITIAL_CAPACITY;	// 设置新数组容量 为 16
            //16 * 0.75
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 设置新数组扩容阀值为 16*0.75 = 12。0.75为负载因子（当元素个数达到容量了4分之3，那么扩容）
        }

        // 新的没有数据的情况，只第一次传递了参数
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                    (int)ft : Integer.MAX_VALUE);  // 参见：PS1
        }
        threshold = newThr; // 设置map的扩容阀值为 新的阀值

        // 创建新的数组（对于第一次添加元素，那么这个数组就是第一个数组；
        // 对于存在oldTab的时候，那么这个数组就是要需要扩容到的新数组）
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;	// 将该map的table属性指向到该新数组

        //oldTab指向地址会改变吗，这里就是引用传递了，A 变了指针，A 覆盖的B的指针汇编吗。


        if (oldTab != null) {// 如果老数组不为空，说明是扩容操作，那么涉及到元素的转移操作
            for (int j = 0; j < oldCap; ++j) { // 遍历老数组
                Node<K,V> e;
                if ((e = oldTab[j]) != null) { // 如果当前位置元素不为空，那么需要转移该元素到新数组
                    oldTab[j] = null; // 释放掉老数组对于要转移走的元素的引用（主要为了使得数组可被回收），已经复制给了e
                    if (e.next == null) // 如果元素没有有下一个节点，说明该元素不存在hash冲突
// PS3
// 把元素存储到新的数组中，存储到数组的哪个位置需要根据hash值和数组长度来进行取模
// 【hash值  %   数组长度】   =    【  hash值   & （数组长度-1）】
//  这种与运算求模的方式要求  数组长度必须是2的N次方，但是可以通过构造函数随意指定初始化容量呀，如果指定了17,15这种，岂不是出问题了就？没关系，最终会通过tableSizeFor方法将用户指定的转化为大于其并且最相近的2的N次方。 15 -> 16、17-> 32
           newTab[e.hash & (newCap - 1)] = e;

// 如果该元素有下一个节点，那么说明该位置上存在一个链表了
// （hash相同的多个元素以链表的方式存储到了老数组的这个位置上了）
// 例如：数组长度为16，那么hash值为1（1%16=1）的和hash值为17（17%16=1）
// 的两个元素都是会存储在数组的第2个位置上（对应数组下标为1），
// 当数组扩容为32（1%32=1）时，hash值为1的还应该存储在新数组的第二个位置上，
// 但是hash值为17（17%32=17）的就应该存储在新数组的第18个位置上了。
// 所以，数组扩容后，所有元素都需要重新计算在新数组中的位置。

//else if (e instanceof TreeNode)  // 如果该节点为TreeNode类型
         //  ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);  // 此处单独展开讨论
  else {
      // preserve order ,保存排序的功能
    Node<K,V> loHead = null, loTail = null;  // 按命名来翻译的话，应该叫低位首尾节点[0,cap-1]
    Node<K,V> hiHead = null, hiTail = null;  // 按命名来翻译的话，应该叫高位首尾节点[cap,newCap-1]
                     // 以上的低位指的是新数组的 0  到 oldCap-1 、高位指定的是oldCap 到 newCap - 1
                        Node<K,V> next;
                       //遍历链表
                        do {
                            //a0
                            next = e.next;
                            // 这一步判断好狠，拿元素的hash值  和  老数组的长度  做与运算
                            // PS3里曾说到，数组的长度一定是2的N次方（例如16），如果hash值和该长度做与运算，结果为0，就说明该hash值和数组长度取模后的值一定小于数组长度（例如mod值为1），
                            // 那么该hash值再和新数组的长度取摸的话mod值也不会放生变化，所以该元素的在新数组的位置和在老数组的位置是相同的，所以该元素可以放置在低位链表中。
                            //说明数组的索引在新的没变化；
                            if ((e.hash & oldCap) == 0) {
                               // PS4
                                if (loTail == null) { // 如果没有尾，说明链表为空
                                    loHead = e;      // 链表为空时，头节点指向该元素，第一个进入的头节点
                                 }
                                else
                                    loTail.next = e;
                                loTail = e;
//                                else{
//                                    loTail.next = e;  // 如果有尾，那么链表不为空，把该元素挂到链表的最后。(第2次的时候loTail和loHead执向同一个内存// )
//                                   }
//                                  loTail = e; // 把尾节点设置为当前元素
                             }

// 如果与运算结果不为0，说明hash值大于老数组长度（例如hash值为17）
// 此时该元素应该放置到新数组的高位位置上
// 例：老数组长度16，那么新数组长度为32，hash为17的应该放置在数组的第17个位置上，也就是下标为16，那么下标为16已经属于高位了，低位是[0-15]，高位是[16-31]
                            else {
                                // 以下逻辑同PS4
                                if (hiTail == null){
                                    hiHead = e;
                                }
                                else{
                                    //第一次的时候HiTail代表那个头节点，执行到链表中第2个节点的时候
                                    //把第一个节点的next指向第2个节点；然后把第2个节点变成尾节点
                                    hiTail.next = e;
                                }
                                hiTail = e;
                            }
                        } while ((e = next) != null);

                        // 低位的元素组成的链表还是放置在原来的位置
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }

                        // 高位的元素组成的链表放置的位置只是在原有位置上偏移了老数组的长度个位置。
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead; // 例：hash为 17 在老数组放置在0下标，在新数组放置在16下标；    hash为 18 在老数组放置在1下标，在新数组放置在17下标；
                         }
                    }
                }
            }
        }
        return newTab; // 返回新数组
    }



    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                        Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }




}
